Có thể tìm các thành phần liên thông trong thời gian tuyến tính bằng thuật toán tìm kiếm theo chiều sâu hoặc tìm kiếm theo chiều rộng.

Các nhà nghiên cứu còn tìm hiểu các thuật toán cho tìm kiếm thành phần liên thông trong những mô hình tính toán giới hạn hơn, chẳng hạn như khi bộ nhớ (không tính phần để lưu trữ dữ liệu vào) là lôgarit của kích thước dữ liệu vào (định nghĩa bởi lớp L). Năm 2008, Reingold đã tìm ra một thuật toán cho việc kiểm tra xem có đường đi giữa hai đỉnh cho trước hay không trong bộ nhớ lôgarit, do đó chứng minh L=SL[1].